//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "algobase.h"
#include "iterator.h"
#include "allocator.h"
#include "forward.h"

FC_NAMESPACE_BEGIN


template <class Allocator>
class vector_pod_base
{
public:
	typedef vector_pod_base<Allocator>				this_type;
	typedef Allocator								allocator_type;

	vector_pod_base()
		: m_begin(0), m_end(0), m_capacity(0), m_allocator()
		{
		}

	explicit vector_pod_base( const allocator_type& alloc )
		: m_begin(0), m_end(0), m_capacity(0), m_allocator(alloc)
		{
		}

	~vector_pod_base()
		{
			deallocate();
		}

	bool empty() const		{ return m_end == m_begin; }
	bool full() const		{ return m_end == m_capacity; }
	size_t size() const		{ return (m_end - m_begin); }
	size_t capacity() const	{ return (m_capacity - m_begin); }
	size_t max_size() const	{ return size_t(-1) / 2; }
	void* begin() const		{ return m_begin; }
	void* end() const		{ return m_end; }

	allocator_type&			get_allocator()			{ return m_allocator; }
	const allocator_type&	get_allocator() const	{ return m_allocator; }
	void set_allocator( const allocator_type& alloc ) { m_allocator = alloc; }

	void clear() { m_end = m_begin; }
	void shrink_to_fit() { set_capacity(m_end - m_begin); }

	void reserve( size_t n )
	{
		if( n > size_t(m_capacity - m_begin) )
			reallocate( n, (void*)m_begin, (void*)m_end );
	}

	void set_capacity( size_t n )
	{
		if( n != size_t(m_capacity - m_begin) )
		{
			const size_t newSize = min( size(), n );
			reallocate( n, (void*)m_begin, (void*)(m_begin + newSize) );
		}
	}

	void resize( size_t n )
	{
		// always respect the initial capacity request by the user.
		reserve(n);

		m_end = m_begin + n;
		//if( n < size() )
		//	erase( m_begin + n, m_end );
	}

	void* insert_uninitialized( void* pos, size_t n )
	{
		FC_ASSERT(pos <= m_end);
		const size_t t = size_t((char*)pos - m_begin);

		if( FC_UNLIKELY(m_capacity < m_end + n) )
		{
			const size_t newCapacity = get_new_capacity(n);
			char* ptr = (char*)allocate(newCapacity);

			const size_t oldSize = size();
			copy_range( (void*)ptr, m_begin, t );
			copy_range( (void*)(ptr + t + n), pos, size_t(m_end - (char*)pos) );
			deallocate();

			// offset pos by t-bytes from new begin.
			pos = (void*)(ptr + t);

			m_begin = ptr;
			m_end = m_begin + oldSize;
			m_capacity = m_begin + newCapacity;
		}
		else
		if( (char*)pos != m_end )
			move_range( (void*)((char*)pos + n), pos, size_t(m_end - (char*)pos) );
			//move_range( (void*)((char*)pos + n), pos, n );

		m_end += n;
		//return (void*)(m_begin + t);
		return pos;
	}

	void erase( void* first, void* last )
	{
		FC_ASSERT(first <= last);

		move_range( first, last, size_t(m_end - (char*)last) );
		m_end -= ((char*)last - (char*)first);
	}

	void* push_back_uninitialized( size_t n )
	{
		if( FC_UNLIKELY(m_end + n > m_capacity) )
			grow(n);

		m_end += n;
		return m_end - n;
	}

	void pop_back( size_t n )
	{
		FC_ASSERT(m_end != m_begin);
		m_end -= n;
	}

	void swap( this_type& x )
	{
		if( m_allocator == x.m_allocator )
		{
			fc::swap( m_begin, x.m_begin );
			fc::swap( m_end, x.m_end );
			fc::swap( m_capacity, x.m_capacity );
		}
		else
		{
			this_type temp(*this);
			*this = x;
			x = temp;
		}
	}

	this_type& operator =( const this_type& x )
	{
		if( this != &x )
		{
			const size_t n = x.size();
			if( capacity() < n )
				reallocate( n, (void*)x.m_begin, (void*)x.m_end );
			else
			{
				copy_range( m_begin, (void*)x.m_begin, n );
				m_end = m_begin + n;
			}
		}

		return *this;
	}

	void* allocate( size_t n )
	{
		return m_allocator.allocate(n);
	}

	void deallocate()
	{
		if( m_begin )
			m_allocator.deallocate( (void*)m_begin, size_t(m_capacity - m_begin) );
	}

	void reallocate( size_t newCapacity, void* first, void* last )
	{
		char* newBegin = (char*)allocate(newCapacity);
		const size_t n = size_t((char*)last - (char*)first);
		if( newCapacity )
		{
			copy_range( (void*)newBegin, first, n );
			deallocate();
		}

		m_begin = newBegin;
		m_end = newBegin + n;
		m_capacity = newBegin + newCapacity;
	}

	void grow( size_t minimumGrowth = 1 )
	{
		size_t newCapacity = get_new_capacity(minimumGrowth);
		reallocate( newCapacity, (void*)m_begin, (void*)m_end );
	}

	void move_range( void* dest, const void* src, size_t n )
	{
		if( n != 0 )
			::memmove(dest, src, n);
	}

	void copy_range( void* dest, const void* src, size_t n )
	{
		if( n != 0 )
			::memcpy(dest, src, n);
	}

	size_t get_new_capacity( size_t minimumGrowth ) const
	{
		const size_t oldCapacity = capacity();
		return fc::max(
			fc::max<size_t>(oldCapacity * 2, oldCapacity + minimumGrowth),
			fc::max<size_t>(minimumGrowth * 2, FC_MIN_VECTOR_GROWTH * FC_DEFAULT_ALIGN)
		);
	}

protected:
	char* m_begin;
	char* m_end;
	char* m_capacity;
	allocator_type m_allocator;

};



template <class T, class Allocator>
class vector_pod : public vector_pod_base<Allocator>
{
public:
	typedef size_t									size_type;
	typedef T										value_type;
	typedef T*										pointer;
	typedef const T*								const_pointer;
	typedef T&										reference;
	typedef const T&								const_reference;
	typedef T*										iterator;
	typedef const T*								const_iterator;
	typedef fc::reverse_iterator<iterator>			reverse_iterator;
	typedef fc::reverse_iterator<const_iterator>	const_reverse_iterator;
	typedef ptrdiff_t								difference_type;
	typedef vector_pod<T, Allocator>				this_type;
	typedef vector_pod_base<Allocator>				base_type;
	typedef typename base_type::allocator_type		allocator_type;

	using base_type::empty;
	using base_type::full;
	using base_type::size;
	using base_type::capacity;
	using base_type::max_size;
	using base_type::clear;
	using base_type::shrink_to_fit;
	using base_type::set_capacity;
	using base_type::get_allocator;
	using base_type::set_allocator;
	using base_type::reallocate;
	using base_type::insert_uninitialized;
	using base_type::push_back_uninitialized;

	using base_type::m_begin;
	using base_type::m_end;
	using base_type::m_capacity;

	vector_pod()
		: base_type()
		{
		}

	explicit vector_pod( const allocator_type& alloc )
		: base_type(alloc)
		{
		}

	explicit vector_pod( size_t n, const T& value = T(), const allocator_type& alloc = allocator_type() )
		: base_type(alloc)
		{
			assign(n, value);
		}

	template<class InputIterator>
		vector_pod( InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type() )
		: base_type(alloc)
		{
			assign( first, last );
		}

	vector_pod( const this_type& x )
		: base_type()
		{
			assign( x.begin(), x.end() );
		}

	/*
	// c++11 support
	//
	//
	#ifdef FC_SUPPORTS_CPP11
	vector( this_type&& x )
		: 
		{
		}

	void swap( this_type&& x);
	vector<T>& operator =( this_type&& x );
	template <typename... Args>
	iterator emplace( const_iterator pos, Args&&... args );
	template <typename... Args>
	void emplace_back( Args&&... args );
	void push_back( T&& x );
	iterator insert( const_iterator pos, T&& x );
	iterator insert( const_iterator pos, fc::initializer_list<T> x );
	const_iterator cbegin() const			{ return const_iterator((T*)m_begin); }
	const_iterator cend() const				{ return const_iterator((T*)m_end); }
	const_reverse_iterator crbegin() const	{ return const_reverse_iterator(end()); }
	const_reverse_iterator crend() const	{ return const_reverse_iterator(begin()); }
	#endif
	*/

	void reserve( size_t n )
	{
		base_type::reserve(n * sizeof(T));
	}

	void resize( size_t n, const T& value = T() )
	{
		size_t oldSize = size();
		base_type::resize( n * sizeof(T) );
		if( n > oldSize )
			fc::fill_n( (T*)m_begin + oldSize, n - oldSize, value );
	}

	void reset() { clear(); }

	reference operator [] ( size_t i ) { return *((T*)m_begin + i); }
	const_reference operator [] ( size_t i ) const { return *((T*)m_begin + i); }

	reference at( size_t i )
	{
		FC_ASSERT(i < size());
		return *((T*)m_begin + i);
	}

	const_reference at( size_t i ) const
	{
		FC_ASSERT(i < size());
		return *((T*)m_begin + i);
	}

	size_t size() const		{ return ((T*)m_end - (T*)m_begin); }
	size_t capacity() const	{ return ((T*)m_capacity - (T*)m_begin); }
	size_t max_size() const	{ return base_type::max_size() / sizeof(T); }

	reference		front()			{ return *(T*)(m_begin); }
	const_reference front() const	{ return *(T*)(m_begin); }
	reference		back()			{ return *((T*)(m_end) - 1); }
	const_reference back()	const	{ return *((T*)(m_end) - 1); }

	iterator		begin()			{ return (T*)(m_begin); }
	const_iterator	begin() const	{ return (T*)(m_begin); }
	iterator		end()			{ return (T*)(m_end); }
	const_iterator	end() const		{ return (T*)(m_end); }
	const_iterator	cbegin() const	{ return (T*)(m_begin); }
	const_iterator	cend() const	{ return (T*)(m_end); }

	reverse_iterator		rbegin()		{ return reverse_iterator(end()); }
	const_reverse_iterator	rbegin() const	{ return const_reverse_iterator(end()); }
	reverse_iterator		rend()			{ return reverse_iterator(begin()); }
	const_reverse_iterator	rend() const	{ return const_reverse_iterator(begin()); }

	pointer data()				{ return (T*)m_begin; }
	const_pointer data() const	{ return (T*)m_begin; }

	void assign( size_t n, const T& value )
	{
		clear();
		insert_n( (T*)m_begin, n, value );
	}

	template <class InputIterator>
	void assign( InputIterator first, InputIterator last )
	{
		AssignDispatch( first, last,
			typename is_integral<InputIterator>::type() );
	}

	template <class InputIterator>
	void assign_iter( InputIterator first, InputIterator last )
	{
		clear();
		insert_iter( (T*)m_begin, first, last );
	}

	iterator insert( iterator it, const T& value )
	{
		FC_ASSERT(iterator_is_valid(it));
		T* p = (T*)base_type::insert_uninitialized( (void*)it, sizeof(T) );
		*p = value;

		return p;
	}

	void insert( iterator it, size_t n, const T& value )
	{
		insert_n( it, n, value );
	}

	template <class InputIterator>
	void insert( iterator it, InputIterator first, InputIterator last )
	{
		InsertDispatch( it, first, last,
			typename is_integral<InputIterator>::type() );
	}

	void insert_n( iterator it, size_t n, const T& value )
	{
		FC_ASSERT(iterator_is_valid(it));

		T* ptr = (T*)base_type::insert_uninitialized( it, n * sizeof(T) );
		fc::fill_n( ptr, n, value );
	}

	template <class InputIterator>
	void insert_iter( iterator it, InputIterator first, InputIterator last )
	{
		FC_ASSERT(!iterator_is_valid(first) && !iterator_is_valid(last));
		FC_ASSERT(iterator_is_valid(it));

		size_t n = distance(first, last);
		T* ptr = (T*)base_type::insert_uninitialized( it, n * sizeof(T) );
		fc::copy( first, last, ptr );
	}

	void insert_at( size_t pos, const T& value )
	{
		insert( (T*)m_begin + pos, value );
	}

	void insert_at( size_t pos, size_t n, const T& value )
	{
		insert( (T*)m_begin + pos, n, value );
	}

	iterator erase( iterator it )
	{
		FC_ASSERT(iterator_is_valid(it));
		base_type::erase( it, it + 1 );
		return it;
	}

	iterator erase( iterator first, iterator last )
	{
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last));
		FC_ASSERT(first <= last);

		base_type::erase( first, last );
		return first;
	}

	iterator erase_unordered( iterator it )
	{
		FC_ASSERT(iterator_is_valid(it));
		*it = back();
		--((T*)m_end);

		return it;
	}

	void erase_unordered_at( size_t pos ) { erase_unordered( (T*)m_begin + pos ); }
	void erase_at( size_t pos ) { erase( (T*)m_begin + pos ); }
	void erase_at( size_t pos, size_t n )
	{
		FC_ASSERT(pos < m_end);
		base_type::erase( (T*)m_begin + pos, (T*)m_begin + pos + n );
	}

	void push_back( const T& value = T() )
	{
		*push_back_uninitialized() = value;
	}

	T* push_back_uninitialized( size_t n = 1 )
	{
		return (T*)base_type::push_back_uninitialized( n * sizeof(T) );
	}

	T* insert_uninitialized( iterator position, size_t n )
	{
		return (T*)base_type::insert_uninitialized( position, n * sizeof(T) );
	}

	void pop_back()
	{
		FC_ASSERT(m_begin != m_end);
		base_type::pop_back( sizeof(T) );
	}

	void push_front( const T& value = T() ) { insert( (T*)m_begin, value ); }
	void pop_front() { erase( (T*)m_begin ); }

	this_type& operator =( const this_type& x )
	{
		return (this_type&)base_type::operator =(x);
	}

	bool iterator_is_valid( const_iterator it ) const
	{
		return (it >= (T*)m_begin && it <= (T*)m_end);
	}

protected:
	template <class InputIterator>
	inline void AssignDispatch( InputIterator first, InputIterator last, const false_type& )
	{
		assign_iter( first, last );
	}

	template <class Integral>
	inline void AssignDispatch( Integral n, Integral value, const true_type& )
	{
		assign( (size_t)n, (T)value );
	}

	template <class Iter>
	inline void InsertDispatch( iterator it, Iter first, Iter last, const false_type& )
	{
		insert_iter( it, first, last );
	}

	template <class Integral>
	inline void InsertDispatch( iterator it, Integral n, Integral value, const true_type& )
	{
		insert_n( it, n, value );
	}

};


// global vector operators

template <class T, class Allocator> inline
	void swap( const vector_pod<T, Allocator>& a, const vector_pod<T, Allocator>& b )
	{
		a.swap(b);
	}

template <class T, class A1, class A2> inline
	bool operator ==( const vector_pod<T, A1>& a, const vector_pod<T, A2>& b )
	{
		return( a.size() == b.size() && fc::equal(a.begin(), a.end(), b.begin()) );
	}

template <class T, class A1, class A2> inline
	bool operator !=( const vector_pod<T, A1>& a, const vector_pod<T, A2>& b )
	{
		return !(a == b);
	}

template <class T, class A1, class A2> inline
	bool operator <( const vector_pod<T, A1>& a, const vector_pod<T, A2>& b )
	{
		return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	}

template <class T, class A1, class A2> inline
	bool operator >( const vector_pod<T, A1>& a, const vector_pod<T, A2>& b )
	{
		return b < a;
	}

template <class T, class A1, class A2> inline
	bool operator <=( const vector_pod<T, A1>& a, const vector_pod<T, A2>& b )
	{
		return !(b < a);
	}

template <class T, class A1, class A2> inline
	bool operator >=( const vector_pod<T, A1>& a, const vector_pod<T, A2>& b )
	{
		return !(a < b);
	}


/*
template <class T> inline
	void swap( const vector_pod<T>& a, const vector_pod<T>& b )
	{
		a.swap(b);
	}

template <class T> inline
	bool operator ==( const vector_pod<T>& a, const vector_pod<T>& b )
	{
		return( a.size() == b.size() && fc::equal(a.begin(), a.end(), b.begin()) );
	}

template <class T> inline
	bool operator !=( const vector_pod<T>& a, const vector_pod<T>& b )
	{
		return !(a == b);
	}

template <class T> inline
	bool operator <( const vector_pod<T>& a, const vector_pod<T>& b )
	{
		return fc::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	}

template <class T> inline
	bool operator >( const vector_pod<T>& a, const vector_pod<T>& b )
	{
		return b < a;
	}

template <class T> inline
	bool operator <=( const vector_pod<T>& a, const vector_pod<T>& b )
	{
		return !(b < a);
	}

template <class T> inline
	bool operator >=( const vector_pod<T>& a, const vector_pod<T>& b )
	{
		return !(a < b);
	}
*/



FC_NAMESPACE_END

